1187C - Vasya And Array - CodeForces Solution

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <math.h>
#include <chrono>
#include <iomanip>
#include <unordered_map>
#include <queue>
using namespace std;
#define ll long long
const int N = 1e2;
const int inf = 1e9;
 
ll gcd(ll a,ll b){
	if(b == 0) return a;
	return gcd(b,a%b);
}

struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
 
bool sortbyCond(const pair<int, int>& a, const pair<int, int>& b){
    if (a.first != b.first) return (a.first < b.first);
    else return (a.second > b.second);
}

// ll mn[N];
// // vector<ll> v(N);
// int dfs(int p) {
// 	if(mn[p] != -1) return mn[p];
// 	if(g[p].size() == 0) return v[p];
// 	ll sum = 0;
// 	for(int i=0;i<(int)g[p].size();i++) {
// 		sum += dfs(g[p][i]);
// 	}
// 	return mn[p] = min(v[p], sum);
// }

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	int pr[n] = {};
	vector<pair<int, int>> v, w;
	for(int i=0;i<m;i++) {
		int t, l, r;
		cin >> t >> l >> r;
		if(t == 1) {
			v.push_back({l, r});
		}
		else {
			w.push_back({l, r});
		}
	}
	sort(v.begin(), v.end());
	int en = 1;
	for(int i=0;i<(int)v.size();i++) {
		if(pr[v[i].first - 1] == 0) {
			en = 1;
		}
		for(int j=v[i].first - 1;j<v[i].second;j++) {
			if(pr[j] == 0) {
				pr[j] = en;
				en++;
			}
		}
	}
	en = 1e5;
	if(pr[0] == 0) {
		pr[0] = en;
	}
	int cnt = 0;
	for(int i=1;i<n;i++) {
		if(pr[i] == 0) {
			if(cnt == 0) {
				pr[i-1] += 1e5;
				cnt++;
			}
			pr[i] = pr[i-1] - 1;
		}
		else {
			cnt = 0;
		}
	}
	int lr = w.size();
	int ck[lr] = {};
	bool ok = false;
	for(int i=1;i<n;i++) {
		if(pr[i] < pr[i-1]) {
			for(int j=0;j<(int)w.size();j++) {
				int p = w[j].first, p1 = w[j].second;
				// cout<<p<<" "<<p1<<" "<<(i)<<" "<<(i + 1)<<"\n";
				if(p <= i && p1 >= (i + 1)) {
					ck[j] = 1;
				}
			}
		}
	}
	for(int i=0;i<lr;i++) {
		if(ck[i] == 0) {
			ok = true;
			break;
		}
	}
	if(ok) cout<<"NO\n";
	else {
		cout<<"YES\n";
		for(int i=0;i<n;i++) {
			cout<<pr[i]<<" ";
		}
	}

}